package com.mid;

/**
 * Created by Lxk on 2020/2/21.
 */
public class Solution397 {

    public int integerReplacement(int n) {
        if (n == 1) {
            return 0;
        }
        if (n % 2 == 0) {
            return integerReplacement(n >>> 1) + 1;
        } else {
            return Math.min(integerReplacement(n + 1), integerReplacement(n - 1)) + 1;
        }
    }

    public static void main(String[] args) {
        Solution397 solution397 = new Solution397();
        System.out.println(solution397.integerReplacement(2147483647));
    }

}
